package org.addsome.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test1 {

    public int hammingDistance(int x, int y) {
        int i = x ^ y;
        int hamming = 0;
        while (i > 0) {
            if (i % 2 == 1) {
                hamming++;
            }
            i = i / 2;
        }
        return hamming;
    }

    public int hammingDistance2(int x, int y) {
        int i = x ^ y;
        int hamming = 0;
        while (i > 0) {
            hamming += i & 1;
            i >>= 1;
        }
        return hamming;
    }

    /**
     * Brian Kernighan 算法
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance3(int x, int y) {
        int i = x ^ y;
        int hamming = 0;
        while (i > 0) {
            i = i & i - 1;
            hamming++;
        }
        return hamming;
    }

    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (shorter == longer) {
            return new int[]{shorter * k};
        }
        int div = longer - shorter;
        int[] ret = new int[k];
        ret[0] = shorter * k;
        for (int i = 1; i <= k; i++) {
            ret[i] = ret[i - 1] + div;
        }
        return ret;
    }

    /**
     * 941. 有效的山脉数组
     *
     * @param arr
     * @return
     */
    public boolean validMountainArray(int[] arr) {
        int length = arr.length;
        int m = 0;
        while (m < length - 1 && arr[m] < arr[m + 1]) {
            m++;
        }
        if (m == 0 || m == length - 1) {
            return false;
        }
        while (m < length - 1 && arr[m] > arr[m + 1]) {
            m++;
        }
        return m == length - 1;
    }

    public boolean isToeplitzMatrix(int[][] matrix) {
        int y = matrix.length;
        int x = matrix[0].length;
        for (int i = 0; i < y; i++) {
            int cur = matrix[i][0];
            for (int i1 = 1; i1 < x && i + i1 < y; i1++) {
                if (matrix[i + i1][i1] != cur) {
                    return false;
                }
            }
        }
        for (int i = 0; i < x; i++) {
            int cur = matrix[0][i];
            for (int j = 0; j < y && i + j < x; j++) {
                if (matrix[j][i + j] != cur) {
                    return false;
                }
            }
        }
        return true;
    }

    public int numSpecial(int[][] mat) {
        int cols = mat[0].length;
        Set<Integer> dupCols = new HashSet<>();
        int count3 = 0;
        for (int i = 0; i < mat.length; i++) {
            int[] col = mat[i];
            int first = -1;
            int count = 0;
            for (int j = 0; j < cols && count < 2; j++) {
                if (col[j] == 1) {
                    count++;
                    first = j;
                }
            }
            if (count == 2 || first == -1||dupCols.contains(first)) {
                continue;
            }
            int count2 = 0;
            for (int j = 0; j < mat.length&& count2 < 2; j++) {
                if (mat[j][first]==1){
                    count2++;
                }
            }
            if (count2 == 2){
                dupCols.add(first);
                continue;
            }
            count3++;
        }
        return count3;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] arr = {1, 2, 3};
        boolean ret = test1.validMountainArray(arr);
        System.out.println(ret);
    }


}
